use crate::stools::{random_array, random_num};
use std::{cmp::Ordering, cmp::PartialOrd, collections::VecDeque};

/// 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
///【要求】
/// 1．pop、push、getMin 操作的时间复杂度都是 O(1)。
/// 2．设计的栈类型可以使用现成的栈结构。
struct MinStack<T> {
    stack: Vec<T>,
    min: Vec<T>,
}
impl<T: Clone + PartialOrd> MinStack<T> {
    fn new() -> Self {
        Self {
            stack: vec![],
            min: vec![],
        }
    }

    fn push(&mut self, elem: T) {
        if self.stack.is_empty() {
            self.stack.push(elem.clone());
            self.min.push(elem);
            return;
        }

        self.stack.push(elem.clone());

        let min_elem = &self.min[self.min.len() - 1];
        let push_elem = if min_elem > &elem {
            elem.clone()
        } else {
            min_elem.clone()
        };
        self.min.push(push_elem);
    }

    fn pop(&mut self) -> Option<(T, T)> {
        if self.stack.is_empty() {
            return None;
        }
        Some((self.stack.pop().unwrap(), self.min.pop().unwrap()))
    }
}

/// 【题目】
/// 编写一个类，用两个栈实现队列，支持队列的基本操作（add、pop、peek）。
struct StackQueue<T> {
    s1: Vec<T>,
    s2: Vec<T>,
}
impl<T: Clone + PartialOrd> StackQueue<T> {
    fn new() -> Self {
        Self {
            s1: vec![],
            s2: vec![],
        }
    }

    fn flash(&mut self) {
        if self.s2.is_empty() {
            while let Some(e1) = self.s1.pop() {
                self.s2.push(e1);
            }
        }
    }

    fn add(&mut self, elem: T) {
        self.flash();
        self.s1.push(elem)
    }

    fn pop(&mut self) -> Option<T> {
        self.flash();
        self.s2.pop()
    }

    fn frist(&mut self) -> Option<&T> {
        self.flash();
        if self.s2.is_empty() {
            None
        } else {
            Some(&self.s2[self.s2.len() - 1])
        }
    }
}

/// 【题目】如何仅用递归函数和栈操作逆序一个栈
/// 一个栈依次压入 1、2、3、4、5，那么从栈顶到栈底分别为 5、4、3、2、1。将这个栈转置
/// 后，从栈顶到栈底为 1、2、3、4、5，也就是实现栈中元素的逆序，但是只能用递归函数来实
/// 现，不能用其他数据结构。
fn get_bottom<T>(stack: &mut Vec<T>) -> T {
    if stack.len() == 1 {
        return stack.pop().unwrap();
    }

    let up = stack.pop().unwrap();
    let bottom = get_bottom(stack);
    stack.push(up);

    bottom
}

fn rev_stack<T>(stack: &mut Vec<T>) {
    if stack.is_empty() {
        return;
    }

    let bottom = get_bottom(stack);
    rev_stack(stack);
    stack.push(bottom)
}

/// 猫狗队列
/// 实现一种狗猫队列的结构，要求如下：
///  用户可以调用 add 方法将 cat 类或 dog 类的实例放入队列中；
///  用户可以调用 pollAll 方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
///  用户可以调用 pollDog 方法，将队列中 dog 类的实例按照进队列的先后顺序依次弹出；
///  用户可以调用 pollCat 方法，将队列中 cat 类的实例按照进队列的先后顺序依次弹出；
///  用户可以调用 isEmpty 方法，检查队列中是否还有 dog 或 cat 的实例；
///  用户可以调用 isDogEmpty 方法，检查队列中是否有 dog 类的实例；
///  用户可以调用 isCatEmpty 方法，检查队列中是否有 cat 类的实例。
#[derive(Debug)]
enum Pet {
    Dog(Dog),
    Cat(Cat),
}
impl PartialEq for Pet {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Pet::Dog(d1), Pet::Dog(d2)) => d1.num == d2.num,
            (Pet::Cat(c1), Pet::Cat(c2)) => c1.num == c2.num,
            _ => false,
        }
    }
}
impl Pet {
    fn num(&self) -> usize {
        match self {
            Pet::Dog(d) => d.num,
            Pet::Cat(c) => c.num,
        }
    }
}

#[derive(Debug)]
struct Dog {
    name: &'static str,
    num: usize,
}
impl Dog {
    fn new() -> Self {
        Self {
            name: "dog",
            num: 0,
        }
    }
    fn set_num(mut self, num: usize) -> Self {
        self.num = num;
        self
    }
}

#[derive(Debug)]
struct Cat {
    name: &'static str,
    num: usize,
}
impl Cat {
    fn new() -> Self {
        Self {
            name: "cat",
            num: 0,
        }
    }
    fn set_num(mut self, num: usize) -> Self {
        self.num = num;
        self
    }
}
struct DogCatQueue {
    dog: VecDeque<Pet>,
    cat: VecDeque<Pet>,
    num: usize,
}
impl DogCatQueue {
    fn new() -> Self {
        Self {
            dog: VecDeque::new(),
            cat: VecDeque::new(),
            num: 0,
        }
    }

    ///  用户可以调用 add 方法将 cat 类或 dog 类的实例放入队列中；
    fn add(&mut self, pet: Pet) {
        self.num += 1;
        match pet {
            Pet::Dog(pet) => self.dog.push_front(Pet::Dog(pet.set_num(self.num))),
            Pet::Cat(pet) => self.cat.push_front(Pet::Cat(pet.set_num(self.num))),
        }
    }

    ///  用户可以调用 pollAll 方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
    fn pop_all(&mut self) -> Option<Pet> {
        if !self.dog.is_empty() && !self.cat.is_empty() {
            if self.dog.back().unwrap().num() > self.cat.back().unwrap().num() {
                self.cat.pop_back()
            } else {
                self.dog.pop_back()
            }
        } else if self.dog.is_empty() {
            self.cat.pop_back()
        } else {
            self.dog.pop_back()
        }
    }

    ///  用户可以调用 pollDog 方法，将队列中 dog 类的实例按照进队列的先后顺序依次弹出；
    fn pop_dog(&mut self) -> Option<Pet> {
        self.dog.pop_back()
    }

    ///  用户可以调用 pollCat 方法，将队列中 cat 类的实例按照进队列的先后顺序依次弹出；
    fn pop_cat(&mut self) -> Option<Pet> {
        self.cat.pop_back()
    }

    ///  用户可以调用 isEmpty 方法，检查队列中是否还有 dog 或 cat 的实例；
    fn is_empty(&self) -> bool {
        self.dog.is_empty() && self.cat.is_empty()
    }

    ///  用户可以调用 isDogEmpty 方法，检查队列中是否有 dog 类的实例；
    fn is_dog_empty(&self) -> bool {
        self.dog.is_empty()
    }
    ///  用户可以调用 isCatEmpty 方法，检查队列中是否有 cat 类的实例。
    fn is_cat_empty(&self) -> bool {
        self.cat.is_empty()
    }
}

/// 用一个栈实现另一个栈的排序
/// 【题目】
/// 一个栈中元素的类型为整型，现在想将该栈从顶到底按从大到小的顺序排序，只许申请一
/// 个栈。除此之外，可以申请新的变量，但不能申请额外的数据结构。如何完成排序？
fn sort_stack<T: PartialOrd>(stack: &mut Vec<T>) {
    if stack.is_empty() {
        return;
    }
    let mut help: Vec<T> = vec![stack.pop().unwrap()];

    while let Some(elem) = stack.pop() {
        while !help.is_empty() && elem > help[help.len() - 1] {
            stack.push(help.pop().unwrap());
        }
        help.push(elem);
    }

    while !help.is_empty() {
        stack.push(help.pop().unwrap());
    }
}

fn hanoi_move(v: &Vec<i32>, idx: usize, start: char, end: char) -> usize {
    println!("{}: {} ----> {}", v[idx], start, end);
    1
}
/// 汉诺塔
fn hanoi(v: &Vec<i32>, idx: usize, start: char, end: char, mid: char) {
    if idx == 0 {
        hanoi_move(v, idx, start, end);
        return;
    }

    hanoi(v, idx - 1, start, mid, end);
    hanoi_move(v, idx, start, end);
    hanoi(v, idx - 1, mid, end, start);
}

/// 汉诺塔增强版
fn hanoi_enhance_move(v: &Vec<i32>, idx: usize, start: char, end: char, mid: char) -> usize {
    println!("{}: {} --{}--> {}", v[idx], start, mid, end);
    2
}

fn hanoi_enhance(v: &Vec<i32>, idx: usize, start: char, end: char, mid: char) -> usize {
    if idx == 0 {
        return hanoi_enhance_move(v, idx, start, end, mid);
    }
    let mut steps: usize = 0;

    steps += hanoi_enhance(v, idx - 1, start, end, mid);
    steps += hanoi_move(v, idx, start, mid);
    steps += hanoi_enhance(v, idx - 1, end, start, mid);
    steps += hanoi_move(v, idx, mid, end);
    steps += hanoi_enhance(v, idx - 1, start, end, mid);

    steps
}

/// 用栈来求解汉诺塔问题
/// 【题目】
/// 汉诺塔问题比较经典，这里修改一下游戏规则：现在限制不能从最左侧的塔直接移动到最
/// 右侧，也不能从最右侧直接移动到最左侧，而是必须经过中间。求当塔有 N 层的时候，打印最
/// 优移动过程和最优移动总步数。
#[derive(Debug, PartialEq, Eq)]
enum Action {
    LtoM,
    MtoL,
    MtoR,
    RtoM,
}

fn hanoi_stack_move(
    preaction: &mut Action,
    non_preaction: Action,
    action: Action,
    fs: &mut Vec<i32>,
    ts: &mut Vec<i32>,
    from: char,
    to: char,
) -> usize {
    if *preaction != non_preaction && fs[fs.len() - 1] < ts[ts.len() - 1] {
        ts.push(fs.pop().unwrap());
        println!("{}: {} --> {}", ts[ts.len() - 1], from, to);
        *preaction = action;
        1
    } else {
        0
    }
}

fn hanoi_stack(num: i32) -> usize {
    let mut ls: Vec<i32> = vec![i32::MAX];
    let mut ms: Vec<i32> = vec![i32::MAX];
    let mut rs: Vec<i32> = vec![i32::MAX];
    let mut steps: usize = 0;
    let mut preaction: Action = Action::LtoM;
    for i in (0..num).rev() {
        ls.push(i);
    }

    while rs.len() != num as usize + 1 {
        steps += hanoi_stack_move(
            &mut preaction,
            Action::MtoL,
            Action::LtoM,
            &mut ls,
            &mut ms,
            'L',
            'M',
        );
        steps += hanoi_stack_move(
            &mut preaction,
            Action::LtoM,
            Action::MtoL,
            &mut ms,
            &mut ls,
            'M',
            'L',
        );
        steps += hanoi_stack_move(
            &mut preaction,
            Action::RtoM,
            Action::MtoR,
            &mut ms,
            &mut rs,
            'M',
            'R',
        );
        steps += hanoi_stack_move(
            &mut preaction,
            Action::MtoR,
            Action::RtoM,
            &mut rs,
            &mut ms,
            'R',
            'M',
        );
    }

    steps
}

/// 生成窗口最大值数组
/// 【题目】
/// 有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
/// 例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为 3 时：
/// [4 3 5] 4 3 3 6 7 窗口中最大值为 5
/// 4 [3 5 4] 3 3 6 7 窗口中最大值为 5
/// 4 3 [5 4 3] 3 6 7 窗口中最大值为 5
/// 4 3 5 [4 3 3] 6 7 窗口中最大值为 4
/// 4 3 5 4 [3 3 6] 7 窗口中最大值为 6
/// 4 3 5 4 3 [3 6 7] 窗口中最大值为 7
/// 如果数组长度为 n，窗口大小为 w，则一共产生 n-w+1 个窗口的最大值。
/// 请实现一个函数:
/// - 输入：整型数组 arr，窗口大小为 w。
/// - 输出：一个长度为 n-w+1 的数组 res，res[i]表示每一种窗口状态下的最大值。
/// 以本题为例，结果应该返回{5,5,5,4,6,7}
fn slide_win_max<T: PartialOrd + Clone>(arr: &[T], w: usize) -> Vec<T> {
    if arr.is_empty() || w == 0 {
        return vec![];
    }

    let mut qmax: VecDeque<usize> = VecDeque::new();
    let mut res: Vec<T> = Vec::new();
    qmax.push_front(0);

    for (idx, elem) in arr.iter().enumerate() {
        while !qmax.is_empty() && *elem >= arr[qmax[qmax.len() - 1]] {
            qmax.pop_back();
        }
        qmax.push_back(idx);
        if qmax[0] + w == idx {
            qmax.pop_front();
        }

        (idx + 1 >= w).then(|| res.push(arr[qmax[0]].clone()));
    }
    res
}

fn slide_win_max_volence<T: PartialOrd + Clone + Ord>(arr: &[T], w: usize) -> Vec<T> {
    if arr.is_empty() || w == 0 {
        return vec![];
    }

    let mut res: Vec<T> = Vec::new();

    for idx in w - 1..arr.len() {
        res.push((arr[idx + 1 - w..=idx].iter().max().unwrap()).clone())
    }
    res
}

/// 单调栈结构
/// 【题目】
/// 给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i]
/// 小的位置。返回所有位置相应的信息。
/// 【举例】
/// arr = {3,4,1,5,6,2,7}
/// 返回如下二维数组作为结果：
/// {
///   {-1, 2},
///   { 0, 2},
///   {-1,-1},
///   { 2, 5},
///   { 3, 5},
///   { 2,-1},
///   { 5,-1}
/// }-1 表示不存在。所以上面的结果表示在 arr 中，0 位置左边和右边离 0 位置最近且值比 arr[0]
/// 小的位置是-1 和 2；1 位置左边和右边离 1 位置最近且值比 arr[1]小的位置是 0 和 2；2 位置左
/// 边和右边离 2 位置最近且值比 arr[2]小的位置是-1 和-1……
/// 进阶问题：给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最
/// 近且值比 arr[i]小的位置。返回所有位置相应的信息。
fn nearest_small_elem<T: PartialOrd>(arr: &[T]) -> Vec<(i32, i32)> {
    if arr.is_empty() {
        return vec![];
    }

    let mut help: Vec<usize> = vec![0];
    let mut res: Vec<(i32, i32)> = vec![(-1, -1); arr.len()];

    for idx in 1..arr.len() {
        while help.len() > 0 && arr[idx] < arr[*help.last().unwrap()] {
            // 被弹出的元素的右侧是idx
            res[help.pop().unwrap()].1 = idx as i32;
        }
        help.push(idx);
        (help.len() > 1).then(|| {
            let last = help.len() - 1;
            res[idx].0 = if arr[help[last]] == arr[help[last - 1]] {
                res[help[last - 1]].0
            } else {
                help[last - 1] as i32
            }
        });
    }

    res
}

fn nearest_small_elem_violence<T: PartialOrd>(arr: &[T]) -> Vec<(i32, i32)> {
    if arr.is_empty() {
        return vec![];
    }
    let mut res: Vec<(i32, i32)> = vec![(-1, -1); arr.len()];

    for idx in 0..arr.len() {
        for lm in (0..idx).rev() {
            if arr[lm] < arr[idx] {
                res[idx].0 = lm as i32;
                break;
            }
        }

        for rm in idx + 1..arr.len() {
            if arr[rm] < arr[idx] {
                res[idx].1 = rm as i32;
                break;
            }
        }
    }

    res
}

/// 求最大子矩阵的大小
/// 【题目】
/// 给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是 1 的所有矩形区域中，最
/// 大的矩形区域为 1 的数量。
/// 例如：
/// 1 1 1 0
/// 其中，最大的矩形区域有 3 个 1，所以返回 3。
/// 再如：
/// 1 0 1 1
/// 1 1 1 1
/// 1 1 1 0
/// 其中，最大的矩形区域有 6 个 1，所以返回 6。
fn find_matrix_violence(
    arr: &Vec<Vec<usize>>,
    x1: usize,
    y1: usize,
    x2: usize,
    y2: usize,
) -> usize {
    let mut sum: usize = 0;
    for x in x1..=x2 {
        for y in y1..=y2 {
            sum += 1;
            if arr[y][x] != 1 {
                return 0;
            }
        }
    }
    sum
}

/// 最大子矩阵暴力解
fn find_max_submatrix_violence(arr: &Vec<Vec<usize>>) -> usize {
    if arr.is_empty() {
        return 0;
    }
    let mut max_matrix = usize::MIN;
    for y1 in 0..arr.len() {
        for x1 in 0..arr[0].len() {
            for y2 in y1..arr.len() {
                for x2 in x1..arr[0].len() {
                    let a = find_matrix_violence(arr, x1, y1, x2, y2);
                    max_matrix = max_matrix.max(a);
                }
            }
        }
    }

    max_matrix
}

/// 用直方图求最大子矩阵，单调栈
fn find_max_submatrix_histogram(arr: &Vec<Vec<usize>>) -> usize {
    if arr.is_empty() || arr[0].is_empty() {
        return 0;
    }

    let mut histogram = vec![0; arr[0].len()];

    let mut max_submatrix: usize = 0;
    for line in arr {
        line.iter().enumerate().for_each(|(idx, &e)| {
            histogram[idx] = if e != 1 { 0 } else { histogram[idx] + 1 };
        });
        let area = histogram_area(&histogram);
        max_submatrix = max_submatrix.max(*area.iter().max().unwrap());
    }

    max_submatrix
}

fn histogram_area(histogram: &[usize]) -> Vec<usize> {
    if histogram.is_empty() {
        return vec![];
    }

    let mut area: Vec<usize> = vec![0; histogram.len()];
    let nearest_small: Vec<(i32, i32)> = nearest_small_elem(&histogram);

    nearest_small.iter().enumerate().for_each(|(idx, &(l, r))| {
        let h = histogram[idx];
        let sl = h * (if l < 0 { idx + 1 } else { idx - l as usize });
        let sr = h * (if r < 0 { histogram.len() } else { r as usize } - (1 + idx));

        area[idx] = sl + sr;
    });

    area
}

/// 最大值减去最小值小于或等于 num 的子数组数量
/// 【题目】
/// 给定数组 arr 和整数 num，共返回有多少个子数组满足如下情况:
/// max(arr[i..j]) - min(arr[i..j]) <= num
/// max(arr[i..j])表示子数组 arr[i..j]中的最大值，min(arr[i..j])表示子数组 arr[i..j]中的最小值。
/// 【要求】
/// 如果数组长度为 N，请实现时间复杂度为 O(N)的解法。
fn find_minmax_subarray_violence(arr: &[i32], num: i32) -> usize {
    if arr.is_empty() {
        return 0;
    }

    let mut num_subarray: usize = 0;
    for i in 0..arr.len() {
        for j in i + 1..=arr.len() {
            if arr[i..j].iter().max().unwrap() - arr[i..j].iter().min().unwrap() <= num {
                num_subarray += 1;
                print!("[暴力] [");
                for idx in i..j {
                    print!(" {}", arr[idx]);
                }
                println!("]");
            }
        }
    }
    num_subarray
}

fn find_minmax_subarray_vecdeque(arr: &[i32], num: i32) -> usize {
    if arr.is_empty() {
        return 0;
    }

    let mut qmax: VecDeque<usize> = VecDeque::new();
    let mut qmin: VecDeque<usize> = VecDeque::new();
    let mut res: usize = 0;

    for i in 0..arr.len() {
        for j in i..arr.len() {
            while let Some(&last) = qmax.back() && arr[j] > arr[last] {
                qmax.pop_back();
            }
            qmax.push_back(j);

            while let Some(&last) = qmin.back() && arr[j] < arr[last] {
                qmin.pop_back();
            }
            qmin.push_back(j);
            if arr[qmax[0]] - arr[qmin[0]] > num {
                qmax.clear();
                qmin.clear();
                break;
            } else {
                print!("[滑窗] [");
                for idx in i..=j {
                    print!(" {}", arr[idx]);
                }
                println!("]");
                res += 1;
            }
        }
    }

    res
}

/// 可见的山峰对数量 【题目】
/// 一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度。
/// 比如， {3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山。
/// 3->1->2->4->5->3 方向叫作 next 方向(逆时针)，
/// 3->5->4->2->1->3 方向叫作 last 方向(顺时针)
/// 问题:给定一个不含有负数但可能含有重复值的数组 arr，返回有多少对山峰能够相互看见
fn find_mountain_pairs(arr: &[usize]) -> usize {
    let mut stack: Vec<(usize, usize)> = vec![];
    let mut pairs: usize = 0;
    let mut end: usize;
    stack.push((arr[0], 1));
    for idx in 1..arr.len() {
        while let Some((h, _)) = stack.last() && *h < arr[idx] {
            stack.pop().map(|(_, k)| {
                pairs += (k > 1).then(|| 2 * k + combine(k, 2)).or(Some(2)).unwrap();
            });
        }
        end = stack.len() - 1;
        if !stack.is_empty() && stack[end].0 == arr[idx] {
            stack[end].1 += 1;
        } else {
            stack.push((arr[idx], 1));
        }
    }

    while let Some((_, k)) = stack.pop() {
        pairs += match stack.len().cmp(&1) {
            Ordering::Greater => (k > 1).then(|| 2 * k + combine(k, 2)).or(Some(2)).unwrap(),
            Ordering::Equal => combine(k, 2) + if stack[0].1 == 1 { 1 * k } else { 2 * k },
            Ordering::Less => (k > 1).then(|| combine(k, 2)).or(Some(0)).unwrap(),
        }
    }

    pairs
}

fn combine(n: usize, m: usize) -> usize {
    if n == 0 || n < m {
        return 0;
    }
    if m == n {
        return 1;
    }
    if m == 1 {
        return n;
    }

    let mut choice: usize = 0;
    choice += combine(n - 1, m);
    choice += combine(n - 1, m - 1);
    choice
}

pub fn coding_main() {
    println!("========== 弹出栈和栈中最小元素 =========");
    let arr = random_array(10, 0..30);
    let mut min_stack = MinStack::new();
    println!("min_stack.pop(): {:?}", min_stack.pop());
    println!("arr: {:?}", arr);
    for elem in &arr {
        min_stack.push(elem);
    }
    println!("弹出栈和最小元素：");
    while let Some((e, m)) = min_stack.pop() {
        print!("({}, {}), ", e, m);
    }
    println!();

    println!("========== 两个栈实现队列 =========");
    let arr = random_array(10, 0..30);
    println!("arr: {:?}", arr);
    let mut queue = StackQueue::new();
    for e in &arr {
        queue.add(e);
    }
    println!("queue.frist() = {:?}", queue.frist());
    print!("队列弹出：");
    while let Some(e) = queue.pop() {
        print!("{} ", e);
    }
    println!();

    println!("========== 用递归逆序一个栈 =========");
    let mut stack = random_array(5, 0..10);
    println!("stack: {:?}", stack);
    rev_stack(&mut stack);
    println!("rev stack: {:?}", stack);

    println!("========== 猫狗队列 =========");
    let mut dog_cat = DogCatQueue::new();
    dog_cat.add(Pet::Dog(Dog::new()));
    dog_cat.add(Pet::Dog(Dog::new()));
    dog_cat.add(Pet::Cat(Cat::new()));
    dog_cat.add(Pet::Cat(Cat::new()));
    dog_cat.add(Pet::Dog(Dog::new()));
    dog_cat.add(Pet::Cat(Cat::new()));
    while let Some(pet) = dog_cat.pop_all() {
        println!("{:?}", pet);
    }

    println!("========== 一个栈实现另一个栈的排序 =========");
    let mut stack = random_array(10, 0..20);
    println!("stack: {:?}", stack);
    sort_stack(&mut stack);
    println!("sort stack: {:?}", stack);

    println!("========== 汉诺塔 =========");
    let v = vec![1, 2, 3];
    hanoi(&v, v.len() - 1, '起', '终', '中');
    println!("========== 汉诺塔(增强) =========");
    let s = hanoi_enhance(&v, v.len() - 1, '起', '终', '中');
    println!("共{}步", s);
    println!("========== 汉诺塔(栈) =========");
    let s = hanoi_stack(3);
    println!("共{}步", s);

    println!("========== 滑动窗口最大值 =========");
    let arr = random_array(10, 0..10);
    let w = random_num(3..5);
    let res = slide_win_max(&arr, w);
    println!("数组：{:?}", arr);
    println!("窗口宽度：{}", w);
    println!("滑动窗口最大值：{:?}", res);

    println!("========== 查找左右两侧距离最近的元素索引 =========");
    let arr = [3, 4, 1, 5, 6, 2, 7];
    let res = nearest_small_elem(&arr);
    println!("arr: {:?}", arr);
    println!("idx: {:?}", res);
    let res = nearest_small_elem_violence(&arr);
    println!("idx: {:?}", res);

    let arr = [49, 60, 60, 44, 70];
    let res1 = nearest_small_elem(&arr);
    println!("array: {:?}", arr);
    println!("res1: {:?}", res1);
    let res2 = nearest_small_elem_violence(&arr);
    println!("res2: {:?}", res2);

    println!("========== 查找最大子矩阵 =========");
    let matrix = vec![
        vec![1, 0, 1, 1, 1],
        vec![1, 1, 1, 1, 1],
        vec![1, 1, 1, 1, 0],
        vec![1, 1, 0, 1, 1],
    ];
    for m in &matrix {
        println!("{:?}", m);
    }

    let x = find_max_submatrix_violence(&matrix);
    println!("最大子矩阵[暴力解]: {:?}", x);
    let x = find_max_submatrix_histogram(&matrix);
    println!("最大子矩阵[直方图]: {:?}", x);

    println!("========== 最大最小相差num的子数组 =========");

    let arr = random_array(5, -10..20);
    let num = random_num(-10..20);
    println!("arr: {:?}", arr);
    println!("num: {:?}", num);
    let pairs = find_minmax_subarray_vecdeque(&arr, num);
    find_minmax_subarray_violence(&arr, num);
    println!("最大最小相关{}的子数组个数：{}", num, pairs);

    println!("========== 可见的山峰对数量 =========");
    // let arr: Vec<usize> = random_array(5, 0..10);
    let arr: Vec<usize> = vec![5, 4, 3, 5, 4, 2, 4, 4, 5, 3, 2];
    println!("环形山：{:?}", arr);
    let pairs = find_mountain_pairs(&arr);
    println!("可见山峰对：{:?}", pairs);
}

#[cfg(test)]
mod 栈与队列 {
    use super::*;

    #[test]
    fn 递归逆序一个栈() {
        for _ in 0..1000 {
            let mut stack = random_array(100, 0..1000);
            let mut stack_rev = vec![];
            for e in stack.iter().rev() {
                stack_rev.push(*e)
            }
            rev_stack(&mut stack);
            assert_eq!(stack, stack_rev);
        }
    }

    #[test]
    fn 猫狗队列() {
        let mut dog_cat = DogCatQueue::new();
        assert_eq!(dog_cat.is_empty(), true);
        assert_eq!(dog_cat.is_dog_empty(), true);
        assert_eq!(dog_cat.is_cat_empty(), true);
        assert_eq!(dog_cat.pop_cat(), None);
        assert_eq!(dog_cat.pop_dog(), None);
        assert_eq!(dog_cat.pop_all(), None);
        dog_cat.add(Pet::Dog(Dog::new()));
        dog_cat.add(Pet::Dog(Dog::new()));
        dog_cat.add(Pet::Cat(Cat::new()));
        dog_cat.add(Pet::Cat(Cat::new()));
        dog_cat.add(Pet::Dog(Dog::new()));
        dog_cat.add(Pet::Cat(Cat::new()));
        assert_eq!(dog_cat.pop_dog(), Some(Pet::Dog(Dog::new().set_num(1))));
        assert_eq!(dog_cat.pop_dog(), Some(Pet::Dog(Dog::new().set_num(2))));
        assert_eq!(dog_cat.pop_dog(), Some(Pet::Dog(Dog::new().set_num(5))));
        assert_eq!(dog_cat.pop_dog(), None);
        assert_eq!(dog_cat.pop_cat(), Some(Pet::Cat(Cat::new().set_num(3))));
        assert_eq!(dog_cat.pop_cat(), Some(Pet::Cat(Cat::new().set_num(4))));
        assert_eq!(dog_cat.pop_cat(), Some(Pet::Cat(Cat::new().set_num(6))));
        assert_eq!(dog_cat.pop_cat(), None);

        dog_cat.add(Pet::Dog(Dog::new()));
        dog_cat.add(Pet::Dog(Dog::new()));
        dog_cat.add(Pet::Cat(Cat::new()));
        dog_cat.add(Pet::Cat(Cat::new()));
        dog_cat.add(Pet::Dog(Dog::new()));
        dog_cat.add(Pet::Cat(Cat::new()));
        assert_eq!(dog_cat.pop_all(), Some(Pet::Dog(Dog::new().set_num(6 + 1))));
        assert_eq!(dog_cat.pop_all(), Some(Pet::Dog(Dog::new().set_num(6 + 2))));
        assert_eq!(dog_cat.pop_all(), Some(Pet::Cat(Cat::new().set_num(6 + 3))));
        assert_eq!(dog_cat.pop_all(), Some(Pet::Cat(Cat::new().set_num(6 + 4))));
        assert_eq!(dog_cat.pop_all(), Some(Pet::Dog(Dog::new().set_num(6 + 5))));
        assert_eq!(dog_cat.pop_all(), Some(Pet::Cat(Cat::new().set_num(6 + 6))));
    }

    #[test]
    fn 一个栈实现另一个栈的排序() {
        for _ in 0..1000 {
            let mut stack = random_array(100, 0..1000);
            let mut stack_random = stack.clone();
            stack.sort();
            sort_stack(&mut stack_random);
            assert_eq!(stack_random, stack);
        }
    }

    #[test]
    fn 滑动窗口最大值() {
        let arr = [4, 3, 5, 4, 3, 3, 6, 7];
        let w = 3;
        let res1 = slide_win_max(&arr, w);
        let res2 = slide_win_max_volence(&arr, w);
        assert_eq!(res1, res2);
        for _ in 0..1000 {
            let arr = random_array(100, 0..100);
            let w = random_num(0..50);
            let res1 = slide_win_max(&arr, w);
            let res2 = slide_win_max_volence(&arr, w);
            assert_eq!(res1, res2);
        }
    }

    #[test]
    fn 左右值小且距离最近的元素索引() {
        for _ in 0..1000 {
            let arr = random_array(100, 0..100);
            let res1 = nearest_small_elem(&arr);
            let res2 = nearest_small_elem_violence(&arr);
            assert_eq!(res1, res2);
        }
    }

    #[test]
    fn 查找最大子矩阵() {
        for _ in 0..1000 {
            let yn: usize = random_num(0..10);
            let xn: usize = random_num(0..10);
            let mut matrix: Vec<Vec<usize>> = vec![];
            for _ in 0..yn {
                matrix.push(random_array(xn, 0..1));
            }
            assert_eq!(
                find_max_submatrix_violence(&matrix),
                find_max_submatrix_histogram(&matrix)
            );
        }
    }

    #[test]
    fn 最大最小相差小于等于num的子数组数量() {
        for _ in 0..1000 {
            let arr = random_array(20, 0..20);
            let num = random_num(0..20);
            assert_eq!(
                find_minmax_subarray_vecdeque(&arr, num),
                find_minmax_subarray_violence(&arr, num)
            );
        }
    }
}
